# 

# 

# **Johnson's Rule（约翰逊法则）详解与Python代码示例**

# 

# **一、Johnson's Rule（约翰逊法则）简介**

# 

# Johnson's Rule（约翰逊法则）是一种用于解决流水作业调度问题的贪心算法。流水作业调度问题通常涉及多台机器和多个作业，目标是找到一种最优的作业加工顺序，使得所有作业完成所需的总时间最短。Johnson's Rule特别适用于两台机器的情况，其中每个作业都需要在这两台机器上按照固定的顺序进行加工。

# 

# Johnson's Rule的基本思想是将所有作业分为两类：M1-型作业和M2-型作业。M1-型作业在机器M1上的加工时间比机器M2上的加工时间短，而M2-型作业则相反。然后，算法首先安排所有M1-型作业在机器M1上加工，接着安排这些作业在机器M2上加工；之后，再安排所有M2-型作业在机器M2上加工，最后安排这些作业在机器M1上加工。这种安排方式可以确保总加工时间最短。

# 

# **二、Python代码示例**

# 

# 下面是一个使用Python实现的Johnson's Rule算法示例。该示例假设我们有两个机器（M1和M2）和一组作业，每个作业在两台机器上的加工时间已知。

# 

# 

# 定义作业在两台机器上的加工时间

jobs = [

    {'name': 'A', 'm1': 2, 'm2': 5},

    {'name': 'B', 'm1': 3, 'm2': 1},

    {'name': 'C', 'm1': 4, 'm2': 3},

    # ... 可以添加更多作业

]



# 根据Johnson's Rule对作业进行分类

def classify_jobs(jobs):

    m1_jobs = [job for job in jobs if job['m1'] < job['m2']]

    m2_jobs = [job for job in jobs if job['m1'] >= job['m2']]

    return m1_jobs, m2_jobs



# 计算总加工时间

def calculate_total_time(m1_jobs, m2_jobs):

    m1_time = sum(job['m1'] for job in m1_jobs)

    m2_time_m1_jobs = max(job['m2'] for job in m1_jobs)

    m2_time = sum(job['m2'] for job in m2_jobs)

    m1_time_m2_jobs = max(job['m1'] for job in m2_jobs)

    return m1_time + m2_time_m1_jobs + m2_time + m1_time_m2_jobs



# 主程序

m1_jobs, m2_jobs = classify_jobs(jobs)

total_time = calculate_total_time(m1_jobs, m2_jobs)



print("M1-型作业:", m1_jobs)

print("M2-型作业:", m2_jobs)

print("总加工时间:", total_time)



# 注释：

# 1. jobs列表定义了每个作业在两台机器上的加工时间。

# 2. classify_jobs函数根据Johnson's Rule对作业进行分类，返回M1-型作业和M2-型作业的列表。

# 3. calculate_total_time函数计算总加工时间，首先计算M1-型作业在M1上的总加工时间，然后找到M1-型作业在M2上的最大加工时间（即M1-型作业在M2上的完成时间），接着计算M2-型作业在M2上的总加工时间，最后找到M2-型作业在M1上的最大加工时间（即M2-型作业在M1上的完成时间）。

# 4. 主程序调用上述函数，并输出结果。
